#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution
{
public:
    int numDecodings(string s)
    {
        vector<int> dp(s.size()+1, -1);
        dp[s.size()] = 1;
        return dfs(s, 0, dp);
    }

    int dfs(string &s, int i, vector<int> &dp)
    {
        if (dp[i] != -1)
            return dp[i];
        if (s[i] == '0')
            return 0;
        else if (i + 1 < s.size() && (s[i] == '1' || s[i] == '2'&& s[i + 1] <= '6'))
        {
            dp[i] = 0;
            dp[i] += dfs(s, i + 1, dp);
            dp[i] += dfs(s, i + 2, dp);
            return dp[i];
        }
        else
        {
            return dp[i] = dfs(s, i + 1, dp);
        }
    }
};

int main()
{
    cout << "Code91" << endl;
    Solution s;
    //cout << s.numDecodings("12") << endl;
    //cout << s.numDecodings("226") << endl;
    //cout << s.numDecodings("0") << endl;
    //cout << s.numDecodings("10") << endl;
    cout << s.numDecodings("11017") << endl;
    return 0;
}